package com.algor;

import javax.crypto.interfaces.PBEKey;
import java.util.Objects;

/**
 * 链表反转
 */
public class ReverseLinkedList {
    /**
     * 定义节点 Node
     */
    static class Node{
        public int value;
        public Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node node5 = new Node(5, null);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        Node curr = node1;
        while (curr != null){
            System.out.printf("%d -> ", curr.value);
            curr = curr.next;
        }
        //curr = reverse(node1);
        curr = recurrence(node1);
        System.out.println();
        System.out.println("反转后的链表：");
        while (curr != null){
            System.out.printf("%d -> ", curr.value);
            curr = curr.next;
        }
    }

    /**
     * 实现反转
     * @param curr 当前节点，传进来的是头结点
     * @return 返回是反转后的头结点
     */
    private static Node reverse(Node curr){
        Node prev = null, next;
        while (Objects.nonNull(curr)){
            //用临时变量保存当前的下一个
            next = curr.next;
            //把当前节点的 next 指向上一个节点
            curr.next = prev;
            //经过前两步操作，当前节点的 next 已经指向下一个了，指针往后移动，prev 变成当前节点
            prev = curr;
            //当前节点则指向刚才临时变量 next，也就是下一个节点
            curr = next;
        }
        return prev;
    }

    private static Node recurrence(Node head){
        if(Objects.isNull(head.next) || Objects.isNull(head)){
            return head;
        }
        Node curr = recurrence(head.next);
        head.next.next = head;
        head.next = null;
        return curr;
    }
}
